//
// Created by victor on 2020/10/16.
//

#include "sort_seq.h"

std::vector<int>& bubble_sort(std::vector<int>& random_vector){

    for(int i=0; i<random_vector.size()-1; i++){
        
        int sorted = false;

        for(int j=0; j<random_vector.size()-1-i; j++){
            
            if(random_vector[j] > random_vector[j+1]){
                
                std::swap(random_vector[j], random_vector[j+1]);
                sorted = true;

            }
        }

        if(!sorted){
            break;
        }
    }

    return random_vector;
}

std::vector<int>& select_sort(std::vector<int>& random_vector){

    for(int i=0; i<random_vector.size()-1; i++){

        int min_index = i;

        for(int j=i+1; j<random_vector.size(); j++ ){
            
            if(random_vector[j] < random_vector[min_index]){
                min_index = j;
            }
        }
        std::swap(random_vector[min_index], random_vector[i]);
    }

    return random_vector;
}

std::vector<int>& insert_sort(std::vector<int>& random_vector){

    for(int i=1; i<random_vector.size(); i++){

        int current = random_vector[i];
        int pre_index = i-1;

        for(; random_vector[pre_index]>current && pre_index>=0; pre_index--){
            random_vector[pre_index+1] = random_vector[pre_index];
        }

        random_vector[pre_index+1] = current;

    }

    return random_vector;
}

std::vector<int>& merge_sort(std::vector<int>& random_vector){

    if(random_vector.size() < 2){
        return random_vector;
    }
    int middle = random_vector.size()/2;
    std::vector<int> left(random_vector.begin(), random_vector.begin()+middle);
    std::vector<int> right(random_vector.begin()+middle, random_vector.end());

    random_vector = merge(merge_sort(left), merge_sort(right));

    return random_vector;
}

std::vector<int> merge(std::vector<int>& left, std::vector<int>& right){

    std::vector<int> merged_vector;

    int left_index=0 , right_index=0;

    for(;left_index<left.size() || right_index<right.size();){

        if(left_index<left.size() && right_index<right.size()){
            if (left[left_index] <= right[right_index]){
                merged_vector.emplace_back(left[left_index]);
                left_index++;
            }
            else{
                merged_vector.emplace_back(right[right_index]);
                right_index++;
            }
        }
        else{
            if(left_index<left.size()){
                merged_vector.emplace_back(left[left_index]);
                left_index++;
            }
            else{
                merged_vector.emplace_back(right[right_index]);
                right_index++;
            }
        }
    }
    return merged_vector;
}

std::vector<int>& merge_sort(std::vector<int>& random_vector) {
    //merge_sort 对输入的random_vector 进行排序， 返回排好序的vector

    //终止条件
    if (random_vector.size() < 2){
        return random_vector;
    }

    //递归函数
    //分左右两块
    int middle = random_vector.size() / 2;
    std::vector<int> left(random_vector.begin(), random_vector.begin() + middle);
    std::vector<int> right(random_vector.begin() + middle, random_vector.end());
    
    std::vector<int> left_sorted = merge_sort(left);
    std::vector<int> right_sorted = merge_sort(right);

    //合并left_sorted、right_sorted
    int left_index = 0;
    int right_index = 0;
    std::vector<int> merge_sorted;
    while (left_index < left_sorted.size() && right_index < right_sorted.size()) {
        if (left_sorted[left_index] < right_sorted[right_index]) {
            merge_sorted.push_back(left_sorted[left_index]);
            left_index++;
        }
        else {
            merge_sorted.push_back(right_sorted[right_index]);
            right_index++;
        }
    }

    while (left_index < left_sorted.size()) {
        merge_sorted.push_back(left_sorted[left_index]);
        left_index++;
    }

    while (right_index < right_sorted.size()) {
        merge_sorted.push_back(right_sorted[right_index]);
        right_index++;
    }
    return merge_sorted;
}

void quick_sort(std::vector<int>& random_vector, int left, int right) {

        if(left>=right){
            return;
        }
        // swap(random_vector[left], random_vector[(left+right)/2]);

        int i = left, j = left+1;
        int base = random_vector[i];

        while(j <= right){

            if(base > random_vector[j]){
                swap(random_vector[++i] ,random_vector[j]);
            }
            j++;
        }
        swap(random_vector[left] , random_vector[i]);

        quick_sort(random_vector, left, i-1);
        quick_sort(random_vector, i+1, right);  
    }

void quick_sort(std::vector<int>& random_vector, int left, int right) {

    if(left>=right){
        return;
    }

    int low = left;
    int high = right;

    int base = random_vector[low];

    for(;low < high;){

        for(; low<high && base<=random_vector[high]; high--){
        }

        random_vector[low] = random_vector[high];

        for(; low<high && base>=random_vector[low]; low++){
        }

        random_vector[high] = random_vector[low];

    }

    random_vector[low] = base;

    printf("sorted: %d %d %d\n", base, low, high);
        for (int i = 0; i < random_vector.size(); i++)
        {

            if (i % 10 == 0 && i != 0)
            {
                printf("\n");
            }
            printf("%d\t", random_vector[i]);
        }
        printf("\n");

    quick_sort(random_vector, left, low-1);
    quick_sort(random_vector, high+1, right);  
}